- Title
- 2-manifold recognition is in logspace
- Creator
- Burton, Benjamin A.; Elder, Murray; Kalka, Arkadius; Tillmann, Stephen
- Relation
- ARC.DP110101104
- Relation
- Journal of Computational Geometry Vol. 7, Issue 1, p. 70-85
- Publisher Link
- http://dx.doi.org/10.20382/jocg.v7i1a4
- Publisher
- Carleton University, Department of Mathematics and Statistics
- Resource Type
- journal article
- Date
- 2016
- Description
- We prove that the homeomorphism problem for 2-manifolds can be decided in logspace. The proof relies on Reingold's logspace solution to the undirected s,t-connectivity problem in graphs.
- Subject
- 2-manifolds; logspace; Reingold's logspace solution
- Identifier
- http://hdl.handle.net/1959.13/1322289
- Identifier
- uon:24552
- Identifier
- ISSN:1920-180X
- Language
- eng
- Full Text
- Reviewed
- Hits: 4902
- Visitors: 5235
- Downloads: 343
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 366 KB | Adobe Acrobat PDF | View Details Download |